Unit 24: Partitional Clustering (K-Means) + Evaluation
1. Introduction
This unit dives deep into the most widely used partitional clustering algorithm:
K-Means Clustering.
We study its optimization objective, the two-step (assignment + update) algorithm, the
initialization problem and solutions (multiple restarts, Bisecting K-Means), and then
switch gears to evaluation measures: Within/Between Sum of Squares, the
Elbow Curve,
and the Silhouette Coefficient.
Learning Objectives
State K-Means' objective function WSS/SSE in closed mathematical form
Execute K-Means manually on a small 2D dataset step-by-step
Explain why K-Means initialization matters and propose two fixes
Derive the Bisecting K-Means procedure
Distinguish Internal (intrinsic) vs External (extrinsic) evaluation paradigms
Compute WSS, BSS, and TSS on a toy dataset; verify WSS + BSS = TSS
Interpret an Elbow/Scree plot and choose an appropriate K
Calculate the silhouette coefficient s(i) for a given point and interpret values
Silhouette Coefficient and average silhouette width
2. Theory
2.1 K-Means Objective: Within-Cluster Sum of Squares
K-Means partitions n data points into K clusters where each point
belongs to the cluster with the nearest centroid (mean). Its objective is to
minimize the Within-Cluster Sum of Squares (WSS), also called the
Sum of Squared Errors (SSE):
\( K \) = number of clusters (must be specified in advance)
\( C_i \) = the i-th cluster (set of assigned points)
\( \mu_i \) = centroid (mean) of cluster i: \( \mu_i = \frac{1}{|C_i|}\sum_{x\in C_i} x \)
\( x \) = a single data point (vector)
\( \|\cdot\|^2 \) = squared Euclidean distance
Intuition: Find K centroids such that each point is as close as possible to its
assigned cluster centroid. K-Means is an iterative optimization algorithm: it starts
with K initial centroids and alternates between two steps until convergence.
2.2 K-Means Algorithm Step-by-Step
Input: Dataset \( D = \{x_1, x_2, \dots, x_n\} \), number of clusters K.
Output: K clusters and their centroids.
1. Initialize: Select K initial centroids \( \{\mu_1, \mu_2, \dots, \mu_K\} \) (randomly or via heuristic).
2. Repeat until convergence:
a) Assignment step: For each point \( x_i \), assign it to cluster
\( j^* = \arg\min_j \| x_i - \mu_j \|^2 \).
b) Update step: For each cluster \( C_j \), recompute its centroid
\( \mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x \).
K-Means is very sensitive to the choice of initial centroids. This matters because K-Means
finds a local optimum, not necessarily the global optimum. Different starting
points can therefore produce different final clusterings. Poor initialization can produce:
Suboptimal cluster assignments (higher WSS)
Empty clusters (if a centroid never wins any point)
Slow convergence (centroids wander before settling)
2.4 Solutions to the Initialization Problem
Strategy 1: Multiple Random Restarts
Strategy 2: Bisecting K-Means
Run K-Means multiple times with different random initial centroid seeds.
Select the result with the lowest WSS/SSE across all runs.
Limitation: Computationally expensive (multiplies cost by the number of restarts) and success not guaranteed.
Start with one cluster containing all data; recursively split clusters into two.
Splits are more stable than full K-Means because each split is a 2-means problem (simpler, less random).
Combines benefits of hierarchical and partitional approaches.
Less sensitive to initialization than flat K-Means.
2.5 Bisecting K-Means Algorithm
Initialize: Place all data points in a single cluster.
Repeat until K clusters are obtained:
a) Select cluster to split: Choose by one of:
Largest WSS / SSE (most internal variance)
Largest number of data points
Random selection (less common)
b) Bisect the selected cluster:
Run basic K-Means with K=2 on the selected cluster.
Perform multiple trials with different random initializations.
Keep the bisection with lowest total SSE.
c) Update cluster list: Remove the original cluster; add the two sub-clusters.
Terminate when the desired K is reached.
2.6 Evaluating Clustering Results
Evaluation is tricky in clustering because there is no single "right answer." The goal is to
compare different clustering experiments and select a good configuration. Two families of
measures exist:
Internal (Intrinsic) Measures
External (Extrinsic) Measures
Evaluate clustering using only the data — no labels required.
Usually depend on the feature representation (scale affects distances).
Examples covered today: WSS (SSE), Between Cluster SS (BSS), Elbow/Scree plot, Silhouette Coefficient.
More examples (Unit 25): Davies-Bouldin, Dunn Index.
Require external knowledge: ground-truth labels or human expert judgements.
Cluster Cohesion: How closely related are objects inside a cluster?
Measured by Within-Cluster Sum of Squares (WSS).
Cluster Separation: How well-separated is one cluster from other clusters?
Measured by Between-Cluster Sum of Squares (BSS).
Formal definitions: Let \(|C_i|\) = size of cluster \(i\), \(m_i\) = centroid of cluster \(i\), and \(m\) = the overall (global) mean of all data points.
To choose K, vary the number of clusters and plot total within-cluster SSE vs K. Look for
an elbow: the K after which the drop in WSS sharply flattens. That elbow
represents a good balance between explanatory power (low WSS) and model simplicity (small K).
Caution: Sometimes there is no clear elbow. Even when there is, interpretation
and decision remain somewhat subjective.
2.10 Silhouette Coefficient
The Silhouette Coefficient evaluates every single point individually: how well is
it located inside its own cluster, versus how separated it is from the other clusters?
Works with any distance metric.
For each point \(d_i\) currently assigned to cluster \(C_i\):
Compute \(a_i\): the average dissimilarity (distance) of \(d_i\) to
all other objects in the same cluster \(C_i\). Small \(a_i\) is good:
the cluster is tight/homogeneous.
For every other cluster \(C_j\) (\(j \neq i\)), compute the average distance
from \(d_i\) to all objects in \(C_j\). The minimum of these
averages is called \(b_i\):
\[
b_i = \min_{j \neq i} \text{avg}_{x \in C_j} d(d_i, x)
\]
\(b_i\) tells us how close \(d_i\) is to the nearest competing cluster.
Larger is better!
Point silhouette for \(d_i\):
\[
s(i) = \frac{b_i - a_i}{\max(a_i, b_i)}
\]
Interpretation of s(i)
s(i) near…
Meaning
+1
ai << bi. Point is very well clustered: tight inside its cluster, far from competitors.
0
ai ≈ bi. Point lies exactly on the decision boundary between its best and second-best cluster.
-1
ai >> bi. Point is likely mis-assigned: would be more similar on average if moved to its neighboring cluster.
Aggregate Silhouette Summaries
Per-cluster average silhouette width:
\[ \bar{s}(C_j) = \frac{1}{|C_j|} \sum_{d_i \in C_j} s(i) \]
Wider is better (cluster 1 "better" than cluster 2 in the lecture figure).
Global average silhouette width:
\[ \text{ASW} = \frac{1}{n} \sum_{i=1}^{n} s(i) \]
Typically maximized over K to pick the number of clusters.
K too high: Natural clusters get split into sub-clusters. Those sub-clusters are still homogeneous (low a_i) but very close to each other (low b_i too) → s(i) shrinks towards 0.
K too low: Separate natural clusters get merged. Within-cluster a_i grows because unrelated points share a centroid → again s(i) shrinks toward 0 or negative.
Right K: Each natural cluster = one cluster. High separation between clusters → high b_i. Tight within clusters → low a_i. → s(i) peaks near +1.
3. Interactive Examples
Example 1: Centroid Update Calculation
After the assignment step of 2D K-Means, cluster C3 contains three points:
\( x_1 = (1, 2) \), \( x_2 = (3, 0) \), \( x_3 = (5, 4) \).
What is the new centroid \( \mu_3 \) after the update step?
You run K-Means with K=4 on a 2D dataset that naturally only has 3 blobs.
What outcome is plausible for the 4th centroid, and how would you fix it?
Reveal Answer
Plausible outcomes:
Empty cluster: the 4th centroid never "wins" any point during assignment → its updated location becomes undefined.
Absorb a few outliers from one of the real blobs, splitting that blob artificially and inflating WSS.
Standard fix in libraries:
Re-initialize the empty-cluster centroid to the point farthest from its current centroid (most misrepresented point), or to the point with highest contribution to WSS from within the largest cluster.
The better solution: lower K and use the Elbow / Silhouette to justify it.
Example 3: WSS+BSS Identity
A clustering on 1D dataset {1,3,5,7,9,11} with K=3 yields clusters C1={1,3}, C2={5,7}, C3={9,11}.
Without computing WSS and BSS individually, what MUST be the numerical value of WSS + BSS?
WSS + BSS = TSS (always!). Global mean m = (1+3+5+7+9+11)/6 = 6.
Therefore WSS + BSS = 70, regardless of the partition.
Example 4: Silhouette Interpretation
Two different K values are tried on the same dataset:
K=2 → ASW = 0.72, with two clusters each showing wide silhouettes near +1.
K=5 → ASW = 0.18, with many individual s(i) near 0 or slightly negative.
Which K is better supported by silhouette evidence? Why?
Reveal Answer
K=2 is clearly better. ASW of 0.72 is high and the per-cluster
silhouettes are wide → strong evidence of compact, well-separated clusters.
K=5's ASW of 0.18 plus the near-zero / negative individual silhouettes indicates
K=5 is too high — natural clusters are being split, causing points
to be close to multiple competing centroids.
4. Numerical Solutions
Problem 1: K-Means Manual Iteration
Run ONE full iteration (assignment + update) of 2D K-Means with K=2.
1D dataset clustered into two clusters:
Cluster X = {1, 2, 7} and Cluster Y = {12, 13}.
Compute the silhouette s(3) for the point at x = 7 (currently in Cluster X).
Use Manhattan distance: d(p, q) = |p - q|.
📘 Step-by-Step Solution
Target point = p = 7 in cluster X = {1,2,7}. Other cluster Y = {12,13}.
Step 1: a_i (avg distance within X, excluding p itself):
Distances from 7 to others in X: |7-1|=6, |7-2|=5. Average = (6+5)/2 = 5.5.
→ a_i = 5.5.
Step 2: b_i (min over other clusters of avg distance to that cluster):
Avg distance from 7 to all of Y: (|7-12|+|7-13|)/2 = (5+6)/2 = 5.5.
Interpretation: s = 0 means this point sits exactly on the decision boundary between the two clusters. It could belong to either with equal justification on average.
5. Try It Yourself
Practice 1: 2nd K-Means Iteration
Using the result of Problem 1 (Section 4):
Data: A(1,1), B(2,1), C(4,3), D(5,4)
Centroids updated at end of iter 1: μ₁ = (1.5, 1.0), μ₂ = (4.5, 3.5)
Perform the assignment step only of iteration 2. Verify whether any point
switches cluster membership, and report the resulting C1, C2 sets.
Point
‖x-μ₁‖²=(x-1.5)²+(y-1)²
‖x-μ₂‖²=(x-4.5)²+(y-3.5)²
Cluster
A(1,1)
(-0.5)²+0=0.25
(-3.5)²+(-2.5)²=12.25+6.25=18.50
C1
B(2,1)
0.5²+0=0.25
(-2.5)²+(-2.5)²=6.25+6.25=12.50
C1
C(4,3)
2.5²+2²=6.25+4=10.25
(-0.5)²+(-0.5)²=0.25+0.25=0.50
C2
D(5,4)
3.5²+3²=12.25+9=21.25
0.5²+0.5²=0.25+0.25=0.50
C2
Assignment unchanged. C1={A,B}, C2={C,D}. No switches → algorithm has converged.
Practice 2: Silhouette of an outlier
Same data as Problem 3 (Section 4): 1D points with Manhattan distance.
Clusters X = {1, 2, 7}, Y = {12, 13}. Compute s(1) for the point at 1 (in X).
a_i: distances from point=1 to {2, 7} = |1-2|=1 and |1-7|=6. Average = (1+6)/2 = 3.5.
b_i: avg distance to Y = {12,13}: (|1-12| + |1-13|)/2 = (11+12)/2 = 11.5.
→ ~0.70, so the point at 1 is reasonably well clustered.
Practice 3: Bisecting K-Means trace
Suppose 6 points have TSS=120 when K=1. We want to reach K=3 using Bisecting K-Means.
First split (K=2) splits into cluster A (WSS=28, 4 points) and cluster B (WSS=15, 2 points).
Which cluster is selected next to split, under the "largest WSS" criterion?
What will the total WSS of K=3 be, assuming the chosen cluster splits into two halves with total new WSS=10?
Selection rule (largest WSS): Cluster A has WSS 28, which is larger than cluster B's WSS 15. So cluster A is split next.
Total WSS at K=3: When we split A into A1+A2 with WSS 10, we remove A's old WSS of 28 and add the new sub-WSS of 10. Cluster B's WSS stays 15:
K-Means minimizes the WSS objective \( \sum_{i=1}^{K}\sum_{x\in C_i}\|x-\mu_i\|^2 \) via a two-step iterative loop: assignment (points → nearest centroid) then update (centroid = mean of cluster).
K-Means only finds a local optimum; initialization matters — use multiple random restarts (pick min WSS) or Bisecting K-Means for stability.
Bisecting K-Means: Start with one cluster; repeatedly 2-means-split the largest-WSS cluster until K clusters; less sensitive to initialization.
Elbow plot of WSS vs K: choose K at the elbow where rate of WSS drops sharply flattens.
Silhouette coefficient s(i) = (b_i - a_i)/max(a_i, b_i) for each point. Range [-1, +1]. High positive = well clustered. Near 0 = on boundary. Negative = likely mis-clustered.
Average Silhouette Width (ASW) peaks at good K; but silhouette is O(n²) and slow on big data.
8. Common Pitfalls
Running K-Means ONCE with random init and trusting it: K-Means is not deterministic! Always run multiple restarts or use Bisecting K-Means / k-means++ (sklearn default).
Forgetting to STANDARDIZE features before K-Means: K-Means is based on Euclidean distance, so unscaled features (e.g., income in $ vs. age in years) dominate the geometry incorrectly.
Using WSS alone: WSS monotonically decreases with K and reaches 0 when K=n. It must be compared to BSS, used in an Elbow plot, or traded off with a penalty (silhouette / gap statistic).
Silhouette sign confusion: (b − a), not (a − b). When b < a, s(i) is negative, not positive.
Misinterpreting empty BSS at K=1: BSS=0 is correct at K=1 (the single centroid equals the global mean). Total TSS = WSS only.
Applying K-Means to non-convex / non-spherical data: K-Means is built on squared Euclidean centroid dispersion. It splits arbitrarily shaped clusters unnaturally (use DBSCAN instead, covered in Unit 25).